package Offer28_101;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 23737
 * @time 2021.9.9
 * 对称二叉树：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 */
public class Test {
    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/*使用队列来实现，虽然过了，但是时空复杂度都很高*/
class SolutionOne {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //首先将根节点的左右结点添加进队列中，因为只有根节点肯定是对称的
        queue.add(root.right);
        queue.add(root.left);
        while (!queue.isEmpty()) {
            //弹出左右结点的值
            TreeNode nodeRight = queue.poll();
            TreeNode nodeLeft = queue.poll();
            //判断是否为空，如果为空，则继续运行。当然返回true也可以
            /*
            这里不能直接返回true是因为，如果输入是
             [9,-42,-42,null,76,76,null,null,13,null,13]或者类似这种的
             都会返回true，其实是不对称的
            */
            if (nodeLeft == null && nodeRight == null) {
                continue;
            }
            //然后开始判断
            if (nodeRight == null || nodeLeft == null || nodeLeft.val != nodeRight.val) {
                return false;
            }
            /*
            这里有个小细节，使用的队列，先进先出的数据结构，所以要先添加右结点的右节点，再添加左节点的左节点
            然后再添加右结点的左节点，最后再添加左节点的右结点
            */
            queue.add(nodeRight.right);
            queue.add(nodeLeft.left);
            queue.add(nodeRight.left);
            queue.add(nodeLeft.right);
        }
        return true;
    }
}

/*使用递归来解答,和我使用的队列是一种思路，只是解法不同*/
class SolutionTwo {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : judgment(root.left, root.right);
    }

    //这里进行递归
    private boolean judgment(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return judgment(left.right, right.left) && judgment(left.left, right.right);
    }
}

/*使用栈来实现*/
class SolutionThree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        /*
            构建 堆栈：
                先将 根节点的左右子节点 入栈
        */
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curNode = root;
        stack.push(curNode.left);
        stack.push(curNode.right);

        /*
            遍历 整棵树：
                1、将 当前栈中 最上面两个节点 弹出，这两个节点对于整棵树来说 一定是 应该对称的
                2、判断 两节点是否都为空，若是，则当前两节点相同，满足对称性质，跳过本轮循环
                3、判断 两节点值是否相等：
                    若不等，返回false
                    若相等，将 两节点的左右子节点，按照对称性质入栈
        */
        while (!stack.isEmpty()) {
            TreeNode leftNode = stack.pop();
            TreeNode rightNode = stack.pop();
            if (leftNode == null && rightNode == null) {
                continue;
            }
            if (leftNode == null || rightNode == null
                    || leftNode.val != rightNode.val) {
                return false;
            }
            stack.push(leftNode.left);
            stack.push(rightNode.right);
            stack.push(leftNode.right);
            stack.push(rightNode.left);
        }
        return true;
    }
}